Annoying Questions I'd Like Answered...

radthemad4 · Post by **radthemad4** » Fri Nov 07, 2014 8:04 pm

Nah, I don't need optimum paths for visiting every part in one go. Just from any one spot to any other. Possibly with some user defined parameters blocking certain paths (e.g. don't show paths involving stairs, or that you can get wet in if it's raining).

Stahlseele · Post by **Stahlseele** » Fri Nov 07, 2014 8:10 pm

Then you would need to compartmentalize every last single variant of a route into "route with stairs" "route without stairs" "route with wet" "route without wet" "route with stairs and wet" "route without stairs and without wet" and "route with stairs and without wet" and "route without stairs and with wet" and then it should just be a simple distance start to target and then chose on user input and add/substract distance?
And should that not mean that you need to go from a to z via either with or without 1wet and 2stairs? And would that not make it into a form of the traveling salesman problem again?
Or am i missing something here?

And that is only for ONE A to B Trip.
If you have 300 class rooms + entrances, exits, toilets, caffeteria, etc, then it becomes an nxn problem for each and any last single one of these trips as well O.o

radthemad4 · Post by **radthemad4** » Fri Nov 07, 2014 8:27 pm

I'll have cartesian coordinates of every room so A* would probably work okay, unless I'm missing something.

Current plan is to implement a navigational mesh with each polygon getting tags like [rain vulnerable] or [stairs]. When a user checks the no stairs box, the system would just ignore all polygons with the stairs tag when computing a route.

(Actually a navigational mesh is probably unnecessary since this isn't a video game. Simple waypoints ought to do it)

name_here · Post by **name_here** » Fri Nov 07, 2014 8:35 pm

It sounds like you want a graph as your underlying datastructure. Put a node in every room and nodes at all the exterior doors and inter-floor paths, then put weighted edges between adjacent rooms on the same floor and link up routes along stairs. If you want to conditionally block routes, mark edges as wet/up-down stairs and ignore them when the parameters are flagged.
Then it's just a graph shortest-path algorithm. Start here.

You could either do a graph on a per-building basis and then A* between buildings, or you could drop nodes along sidewalks or something.

And would that not make it into a form of the traveling salesman problem again?
Or am i missing something here?

Travelling salesman is for when you want to visit every node in a graph in minimum total time. Shortest path between two specific nodes is way the hell easier.

Stahlseele · Post by **Stahlseele** » Fri Nov 07, 2014 8:36 pm

Err, are there elevators around to be used by the students? And not just the oney with a wheelchair with a special key for them?
Because if not, clicking no stairs would make most things inaccessible.
And polygons, why not hexes? or octagons? each of these increases the number of options for progression from 4 to 6 and 8 respectively, if you do not plan on having more than one size and having several others touching sides . .

@name_here
Yes, simple a to b is probably easy enough.
But a to b with or without (in this case rain-risk and stairs) means you don't simply go from a to b but from a to 1 (maybe 2) and then b already, if you need to go somewhere else to not risk stairs and somewhere else in between to not risk rain correct?

name_here · Post by **name_here** » Fri Nov 07, 2014 8:38 pm

Uh, hexes and octagons are polygons. Also, I'm pretty sure that adding more options for progression is literally the opposite of a good thing in pathfinding.

Stahlseele · Post by **Stahlseele** » Fri Nov 07, 2014 8:40 pm

err, right, i get these terms confused sometimes, my bad, carry on <.<

radthemad4 · Post by **radthemad4** » Fri Nov 07, 2014 8:56 pm

Stahlseele wrote:Err, are there elevators around to be used by the students? And not just the oney with a wheelchair with a special key for them?

The buildings are 10 stories tall, and the elevators are open for anyone.

name_here wrote:It sounds like you want a graph as your underlying datastructure. Put a node in every room and nodes at all the exterior doors and inter-floor paths, then put weighted edges between adjacent rooms on the same floor and link up routes along stairs. If you want to conditionally block routes, mark edges as wet/up-down stairs and ignore them when the parameters are flagged.
Then it's just a graph shortest-path algorithm. Start here.

You could either do a graph on a per-building basis and then A* between buildings, or you could drop nodes along sidewalks or something.

Yeah, that'll work great. Thanks. There are a lot of chokepoints in the campus, e.g. all the rooms in some floors are connected to a main corridor and no other rooms, so I'm thinking nested graphs should improve performance.

Prak · Post by **Prak** » Fri Nov 07, 2014 9:51 pm

It's a Uni. You should include a "Walk of Shame" mode that finds the route least likely to run into people, or minimize exposure. Also perhaps a "Walk of Pride" mode, for when you're not ashamed you're wearing last night's clothes because you fucking got laid.

radthemad4 · Post by **radthemad4** » Fri Nov 07, 2014 10:06 pm

Hmm... I suppose I could put some sort of people density property on each node/edge, but I don't know what metric to use or how to measure it.

Come to think of it, maybe I should put in some kind of staircase tolerance thing (e.g. some people are okay with climbing one story in one go, others three, others none, etc. with separate fields for up and down)

name_here · Post by **name_here** » Fri Nov 07, 2014 10:46 pm

Yes, simple a to b is probably easy enough.
But a to b with or without (in this case rain-risk and stairs) means you don't simply go from a to b but from a to 1 (maybe 2) and then b already, if you need to go somewhere else to not risk stairs and somewhere else in between to not risk rain correct?

Doesn't change a thing on the algorithm level. See, the way this works is there's a bunch of nodes connected with edges that have associated weights, and you follow edges originating from one node, and once you have a path from that node to your target node, you just stop calculating other paths once they're longer than the shortest path yet found to your target node. If you want to avoid rain, the algorithm can simply throw out any edges marked as vulnerable to rain and give you the shortest path that isn't vulnerable to rain.

Graph traversal is of course harder than simple linear distance, but there are walls and floors and shit, so you can't just do that.

There are a lot of chokepoints in the campus, e.g. all the rooms in some floors are connected to a main corridor and no other rooms, so I'm thinking nested graphs should improve performance.

Actually, I don't think you want to have separate sub-graphs. Instead of having a "hall" node that links to each classroom node, just only put edges between adjacent classroom nodes on the hall.

If you want more sophisticated parameter analysis than stairs=no, make it so edges can have a stair weight as well as a distance weight.

DSMatticus · Post by **DSMatticus** » Sat Nov 08, 2014 12:33 am

radthemad4 wrote:There are a lot of chokepoints in the campus, e.g. all the rooms in some floors are connected to a main corridor and no other rooms, so I'm thinking nested graphs should improve performance.

name_here wrote:Actually, I don't think you want to have separate sub-graphs. Instead of having a "hall" node that links to each classroom node, just only put edges between adjacent classroom nodes on the hall.

You don't have to do either of these things. Let's talk about a corridor which connects to two other corridors, a stairwell, an elevator, and a dozen rooms. The rooms are all dead-ends, and none of them are your destination. We're going to assume that this corridor is your starting position, but if it isn't then we get to cross off whatever edge you entered the corridor on because we won't be backtracking.

Let's model the corridor as a central node with edges to the other two corridors, the stairwell, the elevator, and each of the twelve nodes. Fully mapping this corridor will require sixteen edge traversals and produce four graphs which could viably continue to your real destination. Remember; the rooms are dead-ends that are not your destination, so we won't backtrack to the central node, we'll just mark those entire paths as failed and move on.

Let's model the corridor as an (almost) linear string of room nodes that branches into the two corridors, the stairwell, and the elevator. Fully mapping this corridor will require fifteen edge traversals (we removed the corridor node, so we have to start in one of the nodes that is actually there, and that reduces the edges traversed by one) and produce four graphs which could viably continue to your real destination. That's (basically) the same number of edge traversals and the same number of viable paths left to work with.

A node with a bunch of edges that lead immediately to dead-ends is virtually painless. You don't need to optimize that. Most of your optimization is going to come from improving your heuristic, because being able to identify failed paths far in advance massively reduces the amount of work you have to do. For example, the path where you alternate stairwells by getting off at each floor and crossing the entire building is going to be a total failure compared to the path where you take the same stairwell the entire time, and the sooner you figure that out the better your algorithm will perform because it gets to prune massive search branches.

Edit: Nested graphs would only be useful if they are isolating genuinely complex structures, such as entire buildings. From the perspective of getting from one end of campus to the other, you probably don't care about every single path through every single building. But some of those buildings are almost certainly going to be in your way, and once you know they're in your way you're going to want to find the quickest way through them. That's a good opportunity to use a nested graph for optimization purposes.

name_here · Post by **name_here** » Sat Nov 08, 2014 1:11 am

Actually your first implementation would be incorrect. The distance from the hallway node to each exit would be independent of the room, which would proceed to spectacularly fuck up your distance calculation. We're talking start at the room closest to one stairwell, go to the far one, then descend a level and walk to the room closest to the first stairwell levels of bad. That will take more nodes or a hell of a lot more edges to fix.

But yes, you do want heuristics that will prune incorrect paths.

Prak · Post by **Prak** » Sat Nov 08, 2014 1:31 am

Ok, random stupidly complicated idea here, but for the population density-

It should be possible (albeit probably very difficult) for the device to somehow ping devices in other areas to determine population density in real time. Population density in real time would be good to know not just for my dumb Walk of Shame suggestion, but also for determining whether a given route is clogged and thus slowly than distance would suggest.

I mean, sure, this relies on people having their phones on them, but most college students have smart devices so that's kind of a low concern limitation.

nockermensch · Post by **nockermensch** » Sat Nov 08, 2014 1:58 am

As others already said, you want to map your campus as a graph. Once you have this mapping done, you can run one of the several well known search algorithms (breadth-first, depth-first, A*) to find the shortest route between any two points.

Ideally, you want two graphs: start with a simple, high level model, like "hall A" connects to "elevator, 1st floor", that connects to "elevator, 4th floor", that connects to "corridor F", that connects to "room 402". (you obviously do this for all corridors / halls / rooms).

With that done for all places you want to cover, you will be able to run a search algorithm and give high level directions, like "from hall A, take the elevator to the fourth floor, then follow the corridor F to find room 402."

To actually draw the path, you'll need a graph with way more nodes overlaid on the campus' 2D or 3D geometry. Basically draw nodes connecting all the entrances and exits in a way that allow you to highlight the paths one would walk. Once this mapping work is done (and this part is boring as fuck) you can use the results found on the simpler graph to prune the searches you'll need to run on the complex graph: For example, if you already know that the path starts on "hall A" and moves to the "elevator, 1st floor", then on the complex graph you find the shortest path from "hall A starting position" to "elevator, 1st floor". From there, you search the path to "elevator, 4th floor", etc.

The complete complex path can then be simply displayed over the map to show 2D walking instructions (like google maps), or be fed to a camera in a 3D viewer, to show the viewer an animation of how to walk there.

DSMatticus · Post by **DSMatticus** » Sat Nov 08, 2014 1:59 am

name_here wrote:We're talking start at the room closest to one stairwell, go to the far one, then descend a level and walk to the room closest to the first stairwell levels of bad.

This is totally true, and definitely a reason to model it room-to-room. I jumped in to comment on the optimization aspect and didn't even bother to think about what the edges were being used for. There's probably a lesson here somewhere.

nockermensch · Post by **nockermensch** » Sat Nov 08, 2014 2:16 am

DSMatticus wrote:
name_here wrote:We're talking start at the room closest to one stairwell, go to the far one, then descend a level and walk to the room closest to the first stairwell levels of bad.
This is totally true, and definitely a reason to model it room-to-room. I jumped in to comment on the optimization aspect and didn't even bother to think about what the edges were being used for. There's probably a lesson here somewhere.

See my description for the solution, then ignore the simpler graph, because it can fall prey to this same kind of fuck-up.

Use just the complex graph (the one overlaid on the campus geography), but now each edge stores the distance between the nodes. You end with a weighted graph, and shortest path algorithms made for these will actually find the shortest possible distance between two points, without fuck-ups like name_here pointed out.

DSMatticus · Post by **DSMatticus** » Sat Nov 08, 2014 3:15 am

You don't really need a separate graph to generate user-friendly instructions, anyway. Once you have a complete path, you're going to pass it through an interpreter that transforms graph traversals into meaningful English instructions. While the behind the scenes model is that you are traversing from room to room to room to room, you're going to want to display that to the user as "go straight until..." or "take the second left, then..."

And that means you will probably need to store some additional information in edges about directionality. Consider an intersection at which each of the four branches contains four rooms. In reality, that graph is a plus sign with a small diamond overlaying the center. The southern room closest to the intersection has an edge to the western room closest to the intersection, and that edge should have a value describing it as "left." And then when you're displaying those as text instructions, you can just collapse all those room-to-room traverals into "take the next left" and proceed from there.

name_here · Post by **name_here** » Sat Nov 08, 2014 3:47 am

Oh, and the general algorithm you want probably is A*. You've got cartesian coordinates, so you can just use the straight-line distance as your heuristic. Ideally, you also want it to understand that you don't get closer to the building next door by going to the classroom closest to the window when you're not on the ground floor, but that's somewhat tricky because buildings may have multiple ground floors.

You also do want to avoid unnecessary stair-changing. Just make sure that your heuristic actually works for all the buildings on campus; college stair layouts can be pretty weird sometimes.

TiaC · Post by **TiaC** » Sat Nov 08, 2014 4:03 am

Hard mode.

name_here · Post by **name_here** » Sat Nov 08, 2014 5:01 am

Fortunately, so long as you don't totally fuck up your heuristic, A* will eventually find the shortest path no matter how stupidly complicated the space.

radthemad4 · Post by **radthemad4** » Sun Nov 09, 2014 3:22 am

Thanks, I'll start working on a demo and post it for feedback.

Koumei · Post by **Koumei** » Sun Nov 09, 2014 8:36 am

Is there a special rule somewhere that when someone refers to something as "a superfood", they're talking total shit and you're allowed to ignore them on the spot? Or do actual real scientists with real degrees and science jobs who aren't just interested in selling you something classify certain things as super-food?

angelfromanotherpin · Post by **angelfromanotherpin** » Sun Nov 09, 2014 8:47 am

Koumei wrote:Or do actual real scientists with real degrees and science jobs who aren't just interested in selling you something classify certain things as super-food?

Nope.

Koumei · Post by **Koumei** » Sun Nov 09, 2014 8:58 am

Good. I assumed it was all horse shit, given the amount of previous things that turned up as "Nope. Maybe add some to your normal balanced mix of food and it won't do any harm", but with ads going "Oh this is a superfood!" and now a news story on camel milk and they keep spouting the term, I really want to just punch them.

That's really kind of them to invent a term to use which is shorthand for "I am a liar, ignore me".